package binaryTree;

import java.util.*;

public class D230719 {
    // 按之字形顺序打印二叉树
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (pRoot == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        boolean flag = true;
        while (!queue.isEmpty()) {
            int count = queue.size();
            Stack<Integer> stack = new Stack<>();   // 通过栈来逆序
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                pRoot = queue.poll();
                if (pRoot.left != null) {
                    queue.add(pRoot.left);
                }
                if (pRoot.right != null) {
                    queue.add(pRoot.right);
                }
                if (flag) {
                    list.add(pRoot.val);
                } else {
                    stack.push(pRoot.val);
                }
            }
            while (!stack.isEmpty()) {
                list.add(stack.pop());
            }
            flag = !flag;
            ret.add(list);
        }
        return ret;
    }

    // 二叉树最大深度
    public int maxDepth (TreeNode root) {
        return dfs(root);
    }
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return Math.max(dfs(node.left), dfs(node.right)) + 1;
    }

    // 二叉树中和为某一值的路径(一)
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum) {
            // 是叶子节点, 且 = sum
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    // 二叉搜索树与双向链表
    // 1. 递归
    TreeNode head,pre;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        dfs2(pRootOfTree);
        return head;
    }
    public void dfs2(TreeNode root){
        if(root == null) {
            return;
        }

        dfs(root.left);

        if (pre != null) {
            pre.right = root;
        } else {
            head = root;
        }
        root.left = pre;
        pre = root;

        dfs(root.right);
    }

    // 2. 中序遍历
    public TreeNode Convert2(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return null;
        }
        // 创建一个栈
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = pRootOfTree;
        TreeNode pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                // 向左走, 并且入栈
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            if (pre != null) {
                // 修改指向
                pre.right = top;
                top.left = pre;
            }
            pre = top;
            cur = top.right;
        }
        while (pRootOfTree.left != null) {
            pRootOfTree = pRootOfTree.left;
        }
        return pRootOfTree;
    }
}
